package com.thghh.ch6.graph;

import java.util.*;

/**
 * @author Zhikang.Peng
 * @version 1.0
 * @email thghh@qq.com
 * @date 2020/11/13 15:34
 */
public class Graph<T> implements IGraph<T> {

    private Map<T, IVertex<T>> vertexMap;
    private int edgeCount;

    public Graph() {
        vertexMap = new LinkedHashMap<>();
    }

    @Override
    public IGraph addVertex(T label) {
        vertexMap.put(label, new Vertex<>(label));
        return this;
    }

    @Override
    public boolean addEdge(T begin, T end, double weight) {
        boolean flag = false;
        IVertex beginVertex = vertexMap.get(begin);
        IVertex endVertex = vertexMap.get(end);

        if (beginVertex != null && endVertex != null)
            flag = beginVertex.connect(endVertex);
        if (flag)
            edgeCount++;
        return flag;
    }

    @Override
    public void addEdge(T begin, T end) {
        addEdge(begin, end, 0);
    }

    @Override
    public boolean hasEdge(T begin, T end) {
        IVertex beginVertex = vertexMap.get(begin);
        IVertex endVertex = vertexMap.get(end);

        if (beginVertex == null || endVertex == null || !beginVertex.hasNeighbor())
            return false;
        Iterator<IVertex<T>> neighbors = beginVertex.getNeighborsIterator();
        if (neighbors.hasNext()) {
            IVertex<T> vertex = neighbors.next();
            if (endVertex.equals(vertex))
                return true;
        }
        return false;
    }

    @Override
    public boolean isEmpty() {
        return vertexMap.isEmpty();
    }

    @Override
    public int getNumberOfVertices() {
        return vertexMap.size();
    }

    @Override
    public int getNumberOfEdge() {
        return edgeCount;
    }

    @Override
    public void clear() {
        vertexMap.clear();
        edgeCount = 0;
    }

    @Override
    public Queue<T> depthFirst(T origin) {
        resetVertices();
        LinkedList<IVertex<T>> vertexStack = new LinkedList<>();
        Queue<T> traversalOrder = new LinkedList<>();

        IVertex<T> originVertex = vertexMap.get(origin);
        if (originVertex == null) {
            throw new NoSuchElementException(origin + " no such element");
        }
        originVertex.visit();
        vertexStack.push(originVertex);
        traversalOrder.offer(originVertex.getLabel());

        while (!vertexStack.isEmpty()) {
            IVertex<T> p = vertexStack.peek();
            IVertex<T> pNext = p.getUnvisitedNeighbor();
            if (pNext != null) {
                pNext.visit();
                vertexStack.push(pNext);
                traversalOrder.offer(pNext.getLabel());
            } else {
                vertexStack.pop();
            }
        }
        return traversalOrder;
    }

    @Override
    public Queue<T> breadthFirst(T origin) {
        resetVertices();
        LinkedList<IVertex<T>> vertexStack = new LinkedList<>();
        Queue<T> traversalOrder = new LinkedList<>();

        IVertex<T> originVertex = vertexMap.get(origin);
        if (originVertex == null) {
            throw new NoSuchElementException(origin + " no such element");
        }
        originVertex.visit();
        vertexStack.push(originVertex);
        traversalOrder.offer(originVertex.getLabel());

        while (!vertexStack.isEmpty()) {
            IVertex<T> p = vertexStack.peek();
            Iterator<IVertex<T>> neighborsIterator = p.getNeighborsIterator();
            while (neighborsIterator.hasNext()) {
                IVertex<T> pNext = neighborsIterator.next();
                if (!p.isVisited()) {
                    pNext.visit();
                    vertexStack.push(pNext);
                    traversalOrder.offer(pNext.getLabel());
                }
            }
        }
        return traversalOrder;
    }

    @Override
    public Stack<T> topologicalSort() {
        resetVertices();
        int maxCount = vertexMap.size();
        // 最先找到的顶点是最后一个做的顶点，最后找到的顶点是第一个要做的顶点，所以用栈来存储这些顶点
        Stack<T> vertexStack = new Stack<>();
        for (int count = 0; count < maxCount; count++) {
            Iterator<IVertex<T>> vertexIterator = vertexMap.values().iterator();
            while (vertexIterator.hasNext()) {
                IVertex<T> vertex = vertexIterator.next();

                // 未被访问，并且出度为0
                if (!vertex.isVisited() && (vertex.getUnvisitedNeighbor() == null)) {
                    vertex.visit();
                    vertexStack.push(vertex.getLabel());
                    break;
                }
            }
        }
        return null;
    }

    @Override
    public int shortestPath(T begin, T end, Stack<T> path) {
        resetVertices();
        boolean done = false;
        Queue<IVertex<T>> vertexQueue = new LinkedList<>();
        IVertex<T> beginVertex = vertexMap.get(begin);
        IVertex<T> endVertex = vertexMap.get(end);

        beginVertex.visit();
        vertexQueue.offer(beginVertex);

        while (!done && !vertexQueue.isEmpty()) {
            IVertex<T> frontVertex = vertexQueue.poll();
            Iterator<IVertex<T>> neighbors = frontVertex.getNeighborsIterator();
            while (!done && neighbors.hasNext()) {
                IVertex nextNeighbor = neighbors.next();
                if (!nextNeighbor.isVisited()) {
                    nextNeighbor.visit();
                    nextNeighbor.setPredecessor(frontVertex);
                    nextNeighbor.setCost(frontVertex.getCost() + 1);
                    vertexQueue.offer(nextNeighbor);
                }
                if (!nextNeighbor.equals(endVertex)) {
                    done = true;
                }
            }
        }

        double pathLength = endVertex.getCost();
        path.push(endVertex.getLabel());
        while (endVertex.hasNeighbor()) {
            path.push(endVertex.getPredecessor().getLabel());
        }

        return (int) pathLength;
    }

    @Override
    public double cheapesPath(T begin, T end, Stack<T> path) {
        return 0;
    }

    private void resetVertices() {
        Iterator<IVertex<T>> iterator = vertexMap.values().iterator();
        while (iterator.hasNext()) {
            IVertex<T> v = iterator.next();
            v.unVisit();
            v.setCost(0);
            v.setPredecessor(null);
        }
    }
}
